package com.potato.study.leetcode.p0628;

import java.util.Arrays;

/**
 * 
 * @author liuzhao11
 * 
 *         628. Maximum Product of Three Numbers
 * 
 *         Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6


Example 2:

Input: [1,2,3,4]
Output: 24


Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
 *
 * 	思路：
 * 		解法：这题的难点主要是要考虑到负数和0的情况。最大乘积可能是最大的3个正数相乘或者是最小的2个负数和最大的1个正数相乘。
 *
 */
public class Solution {

	public int maximumProduct(int[] nums) {
		Arrays.sort(nums);
		int len = nums.length;

		int maxPositive = nums[len - 1] * nums[len - 2] * nums[len - 3];
		int maxNegative = nums[0] * nums[1] * nums[len - 1];

		return maxNegative > maxPositive ? maxNegative : maxPositive;
	}
	
	public static void main(String[] args) {
		Solution solution = new Solution();
//		int[] nums = {1,2,3};
//		int[] nums = {1, 2, 3, 4};
		int[] nums = {-4,-3,-2,-1,60};
		int maximumProduct = solution.maximumProduct(nums);
		System.out.println(maximumProduct);
	}
}
